package algorithm.middle;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 * <p>
 * 整数 a 比整数 b 更接近 x 需要满足：
 * <p>
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-k-closest-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindClosestElements658 {

    /**
     * [0,0,0,1,3,5,6,7,8,8]
     * 2
     * 2
     */

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        LinkedList<Integer> res = new LinkedList<>();
        //1.x小于数组中最小元素
        if (x <= arr[0]) {
            for (int i = 0; i < k; i++) {
                res.add(arr[i]);
            }
            return res;
        }
        //2.x大于数组中最大元素
        if (x >= arr[arr.length - 1]) {
            for (int i = 0; i < k; i++) {
                res.addFirst(arr[arr.length - 1 - i]);
            }
            return res;
        }
        //3.x在数组取值范围之内
        int target = 0;
        int min = Math.abs(arr[0] - x);
        //找到最接近x的元素位置
        for (int i = 0; i < arr.length; i++) {
            if (Math.abs(arr[i] - x) < min) {
                min = Math.abs(arr[i] - x);
                target = i;
            }
        }
        //双指针两边寻找
        int left = target;
        int right = target + 1;
        for (int i = 0; i < k; i++) {
            if (left < 0) {
                while (i < k) {
                    res.addLast(arr[right]);
                    right++;
                    i++;
                }
                break;
            }
            if (right > arr.length - 1) {
                while (i < k) {
                    res.addFirst(arr[left]);
                    left--;
                    i++;
                }
                break;
            }
            if (Math.abs(arr[left] -x) <= Math.abs(arr[right] - x)) {
                res.addFirst(arr[left]);
                left--;
            } else {
                res.addLast(arr[right]);
                right++;
            }
        }
        return res;
    }
}
